#include <vector>
#include <stdexcept>
#include <functional>
#include <iostream>
// 定义堆类 底层采用vector实现 默认大顶堆
template <typename T, typename compare = std::less<T>>
class myHeap
{
private:
    std::vector<T> heap;
    compare cmp;
    // 上浮操作 将最后一个元素上浮到合适的位置
    void up(int index)
    {
        int parent = (index - 1) / 2;
        while (index > 0 && cmp(heap[parent], heap[index])) // 父节点值小于子节点值时 交换 将更大值放在上面
        {
            std::swap(heap[index], heap[parent]);
            index = parent;
            parent = (index - 1) / 2;
        }
    }
    // 下沉操作 删除元素后，将最后一个元素放到堆顶，然后下沉到合适的位置
    void down(int index)
    {
        // int left_index = 2 * index + 1;
        int n = heap.size();
        while (2 * index + 1 < n)
        {
            // 找到左右子节点中较大的一个
            int max_index = 2 * index + 1;
            if (max_index + 1 < n && cmp(heap[max_index], heap[max_index + 1]))
            { // 右子节点存在且大于左子节点
                // 最大节点改为右节点
                max_index++;
            }
            // 如果当前节点小于子节点中的较大值，则交换
            if (cmp(heap[index], heap[max_index]))
            {
                std::swap(heap[index], heap[max_index]);
                // 更新index
                index = max_index;
            }
            else
            {
                break;
            }
        }
    }

public:
    // 构造函数
    myHeap() = default;
    // push
    void push(const T& value)
    {
        heap.push_back(value);
        up(heap.size() - 1);
    }
    // pop
    void pop()
    {
        if(heap.empty())
        {
            throw std::out_of_range("heap is empty");
        }
        // 首尾交换 并删除尾部
        std::swap(heap[0],heap[heap.size()-1]);
        heap.pop_back();
        // 下沉
        down(0);
        
    }
    // top
    T top() const
    {
        if(heap.empty())
        {
            throw std::out_of_range("heap is empty");
        }
        return heap[0];
    }

    // 判断堆是否为空操作 empty
    bool empty() const
    {
        return heap.empty();
    }

    // 返回堆中元素数量操作 size  不能修改非 mutable 成员变量
    size_t size() const
    {
        return heap.size();
    }
    // 析构辅助函数
    // 析构函数
    ~myHeap()
    {
        heap.clear();
    }
};

// 测试函数
void test_myHeap()
{
    myHeap<int> myheap;
    myheap.push(1);
    myheap.push(2);
    myheap.push(3);
    myheap.push(4);
    myheap.push(5);
    myheap.push(6);
    myheap.push(7);
    myheap.push(8);
    myheap.push(9);
    myheap.push(10);
    while (!myheap.empty())
    {
        std::cout << myheap.top() << " ";
        myheap.pop();
    }
    std::cout << std::endl;
}

int main(){
    test_myHeap();
    return 0;
}